home *** CD-ROM | disk | FTP | other *** search
/ Belgian Amiga Club - ADF Collection / BS1 part 27.zip / BS1 part 27 / DiskExpV2.1.adf / DiskExpander_cr / Docs / FAST.doc < prev    next >
Text File  |  1993-08-23  |  9KB  |  195 lines
  1.                                     FAST
  2.                    A fast LZRW based compression algorithm
  3.                                 Version 1.00
  4.                      Copyright 1993 Christian von Roques
  5.  
  6.  
  7.  
  8.                                 Legal issues
  9.                                 ------------
  10.  
  11.     xpkFAST is (C) Copyright 1993 by Christian von Roques.
  12.  
  13.     This package may  be freely distributed,  as long as it  is kept in its
  14. original, complete, and   unmodified form.  It  may not  be distributed  by
  15. itself or in a commercial package of any kind without my permission.
  16.                                                                            
  17.     xpkFAST is distributed in the hope that  it will be useful, but WITHOUT
  18. ANY WARRANTY;  without even  the   implied warranty of  MERCHANTABILITY  or
  19. FITNESS FOR A PARTICULAR PURPOSE.
  20.  
  21.  
  22.                                 Installation
  23.                                 ------------
  24.  
  25.     Make sure the directory libs:compressors  does exist and then just copy
  26. xpkFAST.library  to libs:compressors   .  You  also  need to  have  the XPK
  27. package  installed, it  is  available from  several  sources including Fish
  28. disks.
  29.  
  30.  
  31.                                  Description
  32.                                  -----------
  33.  
  34.     xpkFAST is an  XPK compression sublibrary  whose main purpose is  to be
  35. fast.  The most  interesting part of FAST  is its speedy  compressor, which
  36. makes it predestined for applications which compress about as often as they
  37. decompress.  Good examples  are: backup systems  which make  use  of XPK to
  38. support  compressed backups  or  compressing filesystems.  An  introductory
  39. text  to the concept   of the XPK compression  system  can be  found in the
  40. OVERVIEW document supplied by the standard XPK distribution.
  41.  
  42.     FAST consists  of     three  parts,  two  compressors  and   a   common
  43. decompressor.  You  can choose between  the two compressors by using FAST.0
  44. up to FAST.89 for the ``speedy'' compressor  and FAST.90 up to FAST.100 for
  45. the ``crawling'' compressor, which is  still faster than NUKE.  The default
  46. mode is FAST.50 which selects the ``speedy'' compressor.
  47.  
  48.     Following is a table briefly  listing  some comparative statistics  for
  49. most of  the xpk compression  sublibraries.  These were generated by xBench
  50. on the standard  XPK  benchmark system (A3000/25    with SCRAM, using   the
  51. AmigaVision executable as  data).  Note  that  memory needs don't   include
  52. xpkmaster.library's buffers.
  53.  
  54. Method  Mode     Packing   Unpacking   Packing   Unpacking   Compression
  55.                  Memory     Memory      Speed      Speed        Ratio
  56. ------ -------   -------   ---------   -------   ---------   -----------
  57. FAST    0..89      96K        0K      426 K/s    1048 K/s       32.7%
  58. FAST   90..100     96K        0K       52 K/s    1082 K/s       39.3%
  59.  
  60. RDCN    0..100     ???       ???      217 K/s     800 K/s       33.2%
  61.  
  62. BLZW    0..14       3K        2K      159 K/s     303 K/s       24.4%
  63. BLZW   15..28       7K        4K      141 K/s     328 K/s       29.4%
  64. BLZW   29..42      15K        8K      135 K/s     343 K/s       31.7%
  65. BLZW   43..57      30K       16K      134 K/s     356 K/s       32.4%
  66. BLZW   58..71      60K       32K      139 K/s     364 K/s       32.9%
  67. BLZW   72..85     120K       64K      143 K/s     374 K/s       33.1%
  68. BLZW   86..100    240K      128K      157 K/s     381 K/s       33.7%
  69.  
  70. NUKE    0..100    192K        0K       35 K/s     613 K/s       45.2%
  71.  
  72. IMPL    0..10     300K        0K       29 K/s     360 K/s       34.8%
  73. IMPL   11..30     350K        0K       27 K/s     332 K/s       39.8%
  74. IMPL   31..50     400K        0K       20 K/s     314 K/s       43.3%
  75. IMPL   51..75     425K        0K       14 K/s     300 K/s       44.0%
  76. IMPL   76..98     450K        0K        8 K/s     292 K/s       44.2%
  77. IMPL   99..100    450K        0K        6 K/s     291 K/s       44.3%
  78.  
  79. RLEN    0..100      0K        0K      140 K/s    1043 K/s        4.5%
  80. CBR0    0..100      0K        0K      388 K/s    1833 K/s        3.1%
  81.  
  82.  
  83.     Some Comments to  the above table: Always  remember that these comments
  84. are  just an interpretation of above  table.  There probably are data files
  85. giving totally different results!
  86.  
  87.  *  RDCN is FAST's direct competitor, it gives a bit more compression,
  88.     but is significantly slower. 
  89.  *  If you need a very fast decompression use FAST.
  90.  *  For symmetric applications use either FAST or BLZW.
  91.     [BLZW is always two to three times slower than FAST, but gives a
  92.      little better compression on text files.]
  93.  *  Don't use IMPL, NUKE is faster and gives better compression.
  94.  *  Don't expect too much compression from run length (RLEN, CBR0).
  95.     If you want to use a runlength encoder use CBR0, it's much faster.
  96.  
  97.  
  98.                                   Algorithm
  99.                                   ---------
  100.  
  101.     FAST is a member of the LZ77 family  of datacompressors.  Other popular
  102. members  of the LZ77 family  are:  xpkNUKE, PowerPacker, Imploder (xpkIMPL)
  103. and some parts of lha, gzip, zip, zoo, freeze...
  104.  
  105.     The common thing about all LZ77 compressors is that they store the data
  106. as sequences of <copy>- and <quote>-items.   FAST uses one `control-bit' to
  107. distinguish  between a <copy>- and  a  <quote>-item.  A <quote>-item simply
  108. consists  of  one byte which   has  to be   placed   into the  outputstream
  109. uninterpreted.  Each <copy>-item  consists of 12  bit <distance>- and 4 bit
  110. <length>-information.  <distance>  encodes where to  copy _from_.  The 4095
  111. useful  possibilities   are 1..4095(*)   bytes  back in   the outputstream.
  112. <length> encodes _how_many_   bytes to copy.    The used range is: 3..18  .
  113. Which is encoded as 18-<length>.
  114.  
  115.     The input:  aaaaadadada compresses to: Q(a) C(4,1)  Q(d) C(5,2).  Where
  116. Q(char) means write the character char to the  output and C(len,dist) means
  117. copy len bytes  which can be found  dist  bytes back in  the  output to the
  118. output.
  119.  
  120.     FAST uses two datastreams. That is, the compressed data consists of two
  121. parts, the wordstream and the  bytestream.  The first compressor which uses
  122. this technique was xpkNUKE.  The bytestream starts  at the beginning of the
  123. compressed data and the wordstream is stored in  reverse order beginning at
  124. the  end of the  compressed data.  Thus the  compressed data does look like
  125. this: literalsSSDDRROOWW where   small characters denote  literal bytes and
  126. two capital characters are a word from the wordstream.
  127.  
  128.     If you want to discover more of the internal  workings of xpkFAST just:
  129. ``Use the  force!  Read the  source!''  The  best place  to start your tour
  130. through  the  source is     the decompressor  in decompress.s   since   the
  131. decompressor is much simpler than the compressor.
  132.  
  133. (*)    I could have been using distances of 1..4096, but doing so would
  134.     have added one instruction to the short and thus fast decompressor.
  135.  
  136.  
  137.                                    History
  138.                                    -------
  139.  
  140.     In April 1991, Ross Williams published his LZRW1 algorithm by
  141. presenting it at the data compression conference.
  142.  
  143.     The LZRW1-A algorithm is a direct descendant of the LZRW1 algorithm,
  144. improving it a little in both speed and compression.
  145.  
  146.  
  147.     FAST  started as a ``port''  of Ross Williams' LZRW1-A C-Implementation
  148. and his 68000-version  of the decompressor to  the Amiga as xpksub-library.
  149. While porting I made some  small changes improving the decompression speed.
  150. I  removed  the feature  of handling  the   case of  noncompressable input,
  151. because the xpkmaster.library takes care of that.  After that, I found some
  152. cute changes which   dramatically improved the  speed  of the decompressor.
  153. These were in detail:
  154.  
  155.  *  split the compressed data into a word- and a bytestream, removing many
  156.     double byte accesses with a shift in between.
  157.  *  changed the copy loop from a move-dbra loop to 18 moves in a row.
  158.  *  changed the used range from 1..4096 to 0..4095 eliminating one
  159.     instruction in the decompression loop.
  160.  *  removed all bra.s from the inner decompression loop.
  161.  *  totally rewrote the compressor in 68000 assembler.
  162.     + changed the hashfunction to NOT use mul or div.
  163.     + produces the ``new'' format needed by the new decompressor.
  164.     + removed nearly all of the loop control tests by having
  165.       a fast and a save loop.
  166.     + small code fits into the instructioncache of a 68030. 
  167.  
  168.     Urban Dominik Müller helped me to improve the speed of the compressor
  169. even further, contributing several ideas and  some code.  For details refer
  170. to the source.
  171.  
  172.  
  173.                               Contact Addresses
  174.                               -----------------
  175.  
  176.     Ross Williams
  177.     ross@spam.ua.oz.au
  178.  
  179.  
  180.     Christian von Roques            Christian von Roques
  181.     Forststrasse 71        or        Kastanienweg 4
  182.   D-76131 Karlsruhe                  D-78713 Schramberg
  183.     GERMANY                    GERMANY
  184.  
  185.     roques@karlsruhe.gmd.de (preferred)        IRCnick: Nescum
  186.     roques@juliet.ka.sub.org
  187.  
  188.  
  189.     Urban Dominik Müller
  190.     Schulhausstrasse 83
  191.  CH-6312 Steinhausen
  192.     SCHWEIZ
  193.  
  194.     umueller@amiga.physik.unizh.ch        IRCnick: Zop
  195.